МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОД НЬЮТОНА ДЛЯ РОЗВ’ЯЗУВАННЯ СИСТЕМ НЕЛІНІЙНИХ РІВНЯНЬ
Методичні вказівки
до лабораторної роботи № 5
з курсу
"Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів базових напрямів і 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації",
6.170103 "Управління інформаційною безпекою"
Затверджено
на засіданні кафедри
«Безпека інформаційних
технологій»
Протокол № 12 від 12.05.2011р.
Львів – 2011
Метод Ньютона для розв’язування систем нелінійних рівнянь: Методичні вказівки до лабораторної роботи №5 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації", 6.170103 "Управління інформаційною безпекою" / Укл.: Л.В. Мороз, А.Я. Горпенюк, Н.М. Лужецька - Львів: Видавництво НУ“ЛП”, 2011.- 12 с.
Укладачі: Л.В. Мороз, к.т.н., доц.
А.Я. Горпенюк, к.т.н., доц.
Н.М. Лужецька, асист.
Відповідальний за випуск: В.М. Максимович, д.т.н., проф.
Рецензент: В.В. Хома, д.т.н., проф.
А.Е. Лагун, к.т.н., доц.,
Мета роботи - ознайомлення з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона.
Вступ
Систему нелінійних рівнянь можна зобразити у вигляді
Тобто як функцій від невідомих , причому функції не обов’язково лінійно залежить від змінних .
Позначимо вектор змінних через , а вектор функції через . Тоді систему (1) можна записати у формі.
(1)
Завдання полягає в тому, щоб знайти розв’язок цієї системи. Слід сказати, що на даний час не існує математичної теорії, яка дозволяла б у загальному вигляді розв’язати питання про існування та число розв’язків системи (2). Їх може не бути зовсім, може бути один, декілька або нескінчена множина [3]. Крім того, важливою особливістю системи нелінійних рівнянь є те, що для їх розв’язків не можна використати прямі методи, зокрема, метод послідовного виключення невідомих. Усі розробленні методи є ітераційними, а найефективнішим і широко вживаним є метод Ньютона.
1. Стандартний метод Ньютона
Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем (найчастіше прямими методами).
Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор і розкладемо кожну функцію в ряд Тейлора в околі розв'язку
(2)
де - члени другого і вищих порядків.
Вважаючи, що дуже близьке до , знехтуємо членами вищих порядків і запишемо систему рівнянь в лінеаризованій формі:
(3)
або в іншому вигляді
(4)
де – матриця Якобі (якобіан) системи (1)
Враховуючи, що є розв'язком системи, згідно з (2) можемо записати:
Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:
(5)
Розв'язком системи (5) є нове значення вектора X, яке не точно дорівнює значенню вектора (оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати
(6)
Звідси
(7)
де - обернена матриця Якобі; .
У достатньо широкому околі розв'язку ітераційний процес (7) збігається, якщо .
Ітераційний процес закінчується при виконанні умови
(8)
де Σ - задана гранична похибка уточнень коренів системи (1).
Таким чином, алгоритм стандартного методу Ньютона можна розбити на декілька кроків.
Крок 1. Вибір вектора початкових уточнень
.
Крок 2. Обчислення елементів матриці Якобі.
Крок 3. Обчислення елементів оберненої матриці Якобі.
Крок 4. Перемноження значень функції (див. формулу (7))
Крок 5. Одержаний на кроці 4 вектор віднімається від вектора , у результаті чого одержується покращений вектор розв'язку .
Крок 6. Перевірка умови закінчення ітерацій (8). Якщо вона не виконується, то за вектор початкових уточнень приймається вектор і проводиться наст...